package graph.traversal;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname : AllPathsFromSourceLeadToDestination
 * @Description : <a href="https://leetcode.cn/problems/all-paths-from-source-lead-to-destination/">1059. 从始点到终点的所有路径</a>
 * 无权有向图：深度优先搜索 + 记忆搜索
 * @Author : chentianyu
 * @Date 2023/2/4 23:44
 */


public class AllPathsFromSourceLeadToDestination {
    private final int VISITED = 1;
    private final int SUCCESS = 2;
    private final int FAILED = 3;

    List<List<Integer>> matrix;  // 邻接矩阵
    int[] visited;  // 记录遍历状态 + 记忆搜索

    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        // 建立邻接矩阵
        matrix = new ArrayList<>();
        for (int i = 0; i < n; i++) matrix.add(new ArrayList<>());
        for (int[] edge : edges) matrix.get(edge[0]).add(edge[1]);

        // 若目标节点还有后续边，肯定不满足要求
        if (!matrix.get(destination).isEmpty()) return false;

        // 深度优先搜索
        visited = new int[n];
        return dfs(source, destination);
    }

    private boolean dfs(int cur, int destination) {
        // 记忆搜索判断：
        if (visited[cur] == SUCCESS) return true;
        if (visited[cur] == FAILED) return false;

        // 正确情况：当前节点等于目标节点（因为已经排除目标节点有后续边）
        if (cur == destination) {
            visited[cur] = SUCCESS;
            return true;
        }
        // 错误情况：存在其他终点 或 有环
        if (matrix.get(cur).isEmpty() || visited[cur] == VISITED) {
            visited[cur] = FAILED;
            return false;
        }

        // 使用记忆搜索便无需回溯，因为当前节点再次被遍历时直接使用记忆结果
        visited[cur] = VISITED;
        for (Integer next : matrix.get(cur)) {
            if (!dfs(next, destination)) {
                visited[cur] = FAILED;
                return false;
            }
        }
        visited[cur] = SUCCESS;
        return true;
    }
}
